package leetcode.helper.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 打家劫舍测试用
 *
 * @author Max
 * @date 2021年8月19日
 * @description 337.打家劫舍 III <br>
 */
public class TreeArray {

	public static void main(String[] args) {
//		Integer[] array = new Integer[] { 3, 2, 3, null, 3, null, 1 };
		Integer[] array = new Integer[] { 4, 1, null, 2, null, 3 };
		TreeArray ta = new TreeArray();
		TreeNode root = TreeArray.array2tree(array);
		System.out.println(root);
		Integer[] array1 = TreeArray.tree2array(root);
		System.out.println(array1);
		System.out.println(treeheight(root));

	}

	public static int treeheight(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = treeheight(root.left);
		int right = treeheight(root.right);
		return left + right + 1;
	}

	/**
	 * 宽度数组
	 *
	 * @param root
	 * @return
	 */
	public static Integer[] tree2array(TreeNode root) {
		if (root == null)
			return null;
		Queue<TreeNode> result = new LinkedList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			result.add(node);
			if (node == null) {
				continue;
			}
			if (node.left != null || node.right != null) {
				queue.add(node.left);
				queue.add(node.right);
			}
		}
		int len = result.size();
		Integer[] array = new Integer[len];
		for (int i = 0; i < len; i++) {
			TreeNode node = result.poll();
			if (node == null) {
				array[i] = null;
			} else {
				array[i] = node.val;
			}
		}
		return array;
	}

	public static TreeNode array2tree(Integer[] array) {
		if (array == null || array.length == 0)
			return null;
		TreeNode root = new TreeNode();
		root.val = array[0];
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		int point = 1;
		int size = array.length;
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (point < size) {
				Integer pi = array[point++];
				if (pi == null) {
					node.left = null;
				} else {
					TreeNode left = new TreeNode();
					left.val = pi;
					node.left = left;
					queue.add(left);
				}

			}
			if (point < size) {
				Integer pi = array[point++];
				if (pi == null) {
					node.right = null;
				} else {
					TreeNode right = new TreeNode();
					right.val = pi;
					node.right = right;
					queue.add(right);
				}

			}

		}
		return root;
	}

	public TreeNode[] tree2arrayNode(TreeNode root) {
		if (root == null)
			return null;
		Queue<TreeNode> result = new LinkedList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			result.add(node);
			if (node == null) {
				continue;
			}
			if (node.left != null || node.right != null) {
				queue.add(node.left);
				queue.add(node.right);
			}
		}
		int len = result.size();
		TreeNode[] array = new TreeNode[len];
		for (int i = 0; i < len; i++) {
			TreeNode node = result.poll();
			if (node == null) {
				array[i] = null;
			} else {
				array[i] = node;
			}
		}
		return array;
	}

}
